package io.github.hadyang.leetcode.random;

import org.junit.Assert;
import org.junit.Test;

/**
 * 乘积最大子序列
 *
 * <p>给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
 *
 * <p>示例 1:
 *
 * <p>输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。 示例 2:
 *
 * <p>输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-product-subarray
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q152 {

  public int maxProduct(int[] nums) {
    int max = nums[0];
    int min = nums[0];
    int res = max;

    for (int i = 1; i < nums.length; i++) {
      int num = nums[i];
      int a = num * min;
      int b = num * max;
      max = Math.max(num, Math.max(b, a));
      min = Math.min(num, Math.min(b, a));

      res = Math.max(res, max);
    }

    return res;
  }

  @Test
  public void test() {
    Assert.assertEquals(6, maxProduct(new int[] {2, 3, -2, 4}));
    Assert.assertEquals(0, maxProduct(new int[] {-2, 0, -1}));
    Assert.assertEquals(0, maxProduct(new int[] {0, -1}));
    Assert.assertEquals(2, maxProduct(new int[] {0, 2}));
  }
}
